package classical_problems_150;

public class P_0167 {

    /*
    * 解题思路：
    * 数组本身已经非递减排序了，那么就可以从前后两头开始遍历
    * 对于前面的numbers[i]，可以在(i+1 ,numbers.length-1)的范围查找有无匹配的数
    *
    * 进一步优化的空间：
    *   查找范围的右边界也可是可以不断左移的，可以修改binarySearch，使其返回小于等于target的第一个下标
    *   该下标可以作为新的右边界
    *
    *
    * */

    // 递归的二分查找
    private int binarySearch(int[] nums, int left, int right, int target){
        if(left > right) return -1;
        if(right == left){
            if(nums[left]==target) return left;
            else return -1;
        }
        int mid=(right + left) / 2;
        if(nums[mid] == target) return mid;
        else if (nums[mid] > target) return binarySearch(nums, left, mid-1, target);
        else return binarySearch(nums, mid+1, right, target);

    }

    // 非递归的二分查找
    private int binarySearch(int[] nums, int start, int target){
        int left=start;
        int right=nums.length-1;
        while(left<=right){
            int mid=(left + right) /2;
            if(nums[mid]<target){
                left = mid+1;
            } else if(nums[mid] > target){
                right = mid-1;
            } else {
                return mid;
            }
        }

        return -1;
    }

    public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        for(int i=0; i<numbers.length; i++){
            int index = binarySearch(numbers, i+1, target-numbers[i]);
            if(index>=0){
                res[0] = i+1;
                res[1] = index+1;
            }
        }
        return res;
    }
}
